102

Literature

Aaranson S (2003) Is P versus NP formally independent? Bull EATCS 2003(81):109–136

Aaranson S (2005) NP-complete problems and physical reality. SIGACT News Complex Theory

Column 36(1):30–52. arXiv:quant-ph/0502072v2 (* Both works are not only enjoyable to read,

but take care of NP problems solidly and accurately)

Chaitin GC (2006) Limits of reason. Scientific Am 294(3):74–81. (* Very nice introduction to

boundaries for human and computer decision making)

Cook S (1971) The complexity of theorem proving procedures. In: Proceedings of the third annual

ACM symposium on theory of computing. ACMS, New York, pp 151–158

Hodges A (2014) Alan Turing: the enigma vintage. Random House, London

Levin L (1973) Universal search problems (Russian: Унивepcaльныe зaдaчипepeбopa,

Universal’nyeperebornyezadachi).

Problems

of

Information

Transmission

(Russian:

Пpoблeмыпepeдaчиинфopмaции,

ProblemyPeredachiInformatsii)

9(3):115–116

(pdf)

(Russian), (Englische Ausgabe: Trakhtenbrot BA (1984) A survey of Russian approaches to pere­

bor (brute-force searches) algorithms. Ann Hist Comput 6(4):384–400. https://doi.org/10.1109/

MAHC.1984.10036)

8  When Does the Computer Stop Calculating?